package 题目集.位运算.集合论;

import org.junit.Test;
import 题目集.滑动窗口.demo02_找到按位或最接近K的子数组;

/**
 * https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/description/?envType=daily-question&envId=2024-10-09
 * 给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，
 * 满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。
 * 请你返回 最小 的绝对差值。
 * 子数组 是数组中连续的 非空 元素序列。
 */
public class demo01_找到按位或最接近K的子数组 {
    @Test
    public void t1() {
        int[] nums = {3, 3, 8};
        System.out.println(minimumDifference(nums, 8) == 0);
    }

    @Test
    public void t2() {
        int[] nums = {42, 70, 64, 40, 36};
        System.out.println(minimumDifference(nums, 88) == 16);
    }

    @Test
    public void t3() {
        int[] nums = {1, 2, 4, 5};
        System.out.println(minimumDifference(nums, 3));
    }

    /**
     * 暴力解
     *
     * @param nums
     * @param k
     * @return
     */
    public int minimumDifference1(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            res = Math.min(res, Math.abs(k - nums[i]));
            int temp = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                temp |= nums[j];
                res = Math.min(res, Math.abs(k - temp));
            }
        }
        return res;
    }

    /*暴力解法2*/
    public int minimumDifference2(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            res = Math.min(res, Math.abs(k - nums[i]));
            for (int j = i - 1; j >= 0; j--) {
                nums[j] |= nums[i];
                res = Math.min(res, Math.abs(k - nums[j]));
            }
        }
        return res;
    }

    /**
     * 集合论：我们把每个数都看成一个集合（位图），每个数相当于是由位图中每个1构成的集合。
     * 当我们进行与操作时，是对两个集合求交集
     * 当我们进行或操作时，是对两个集合求并集
     * <p>
     * 对于上面的暴力解法1，其实就是枚举所有[j~i]的并集。
     * 假设我们把每个位置到 (i-1)的并集保存起来，我们如何得到所有位置到i的并集？
     * 我们还是得一个一个的向前进行并运算，例如暴力解法2
     * 但是！！如果set[j~(i-1)]是nums[i]的父集，那么set[j~i]的值会变吗？当然不会，因为并自己的子集等于自己。
     * 那么既然如此，前面的那些set还需要与nums[i]进行并集操作码？
     * 当然不需要，因为前面的数都是 set[j~(i-1)]的父集，而set[j~(i-1)]又是nums[i]的父集，并上nums[i]，也只是并自己的子集。所以他们不会发生改变。
     * <p>
     * 最终代码如下
     *
     * 时间复杂度：O(nlogV)，V是范围最大值。
     *
     * 这题还有滑动窗口的解法：{@link demo02_找到按位或最接近K的子数组#minimumDifference(int[], int)}
     * @return
     */
    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            /**
             * set[i~i]=nums[i]
             * 而自己是自己的子集，所以需要单独处理
             */
            res = Math.min(res, Math.abs(k - nums[i]));
            for (int j = i - 1; j >= 0; j--) {
                /*条件成立说明nums[i]是set[j~（i-1）]的子集*/
                if ((nums[j] | nums[i]) == nums[j]) break;
                /*nums[i]不是set[j~(i-1)]的子集，则加入到set[j~(i-1)]中*/
                /*每执行一步，都会把前面的集合扩张一些，所以最多扩张logV位*/
                nums[j] |= nums[i];
                res = Math.min(res, Math.abs(nums[j] - k));
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
